package BinarySearch;

public class _33_SearchinRotatedSortedArray {
    public int search(int[] nums, int target) {
        if (nums.length == 0) {
            return -1;
        }
        int pivot = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                pivot = i + 1;
                break;
            }
        }
        int start = 0, pivot2 = pivot, end = nums.length - 1;
        while (start < pivot) {
            int middle = start + (pivot - start) / 2;
            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] < target) {
                start = middle + 1;
            } else {
                pivot = middle;
            }
        }
        while (pivot2 < end) {
            int middle = pivot2 + (end - pivot2) / 2;
            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] < target) {
                pivot2 = middle + 1;
            } else {
                end = middle;
            }
        }

        return nums[start] == target ? start : nums[end] == target ? end : -1;
    }
}
